A virtual machine monitor (VMM), such as a hypervisor, is a program that creates virtual machines, each with virtualized hardware resources which may be backed by underlying physical hardware resources. To virtualize memory, the VMM can implement virtual translation look-aside buffers (TLBs) that cache address translations from page tables specified by guest operating systems, much like a TLB in a physical processor. However, some operations associated with such virtual TLBs may be costly, since virtualization may entail several layers of translations between virtual memories (such as guest and hypervisor virtual memories) and physical memories (such as guest and system physical memories). Furthermore, virtual TLBs may consist of a large number of shadow page tables, so it may be impractical to implement one TLB for each virtual processor. Thus, it would be advantageous to provide mechanisms that could cope with virtual machines that have multi-processor architectures and share a virtual TLB between more than one virtual processor in an efficient and scalable manner.